import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Algorithm{
 	static void Random(NewState state){
 		List<Planet> myPlanets = state.MyPlanets();
 		List<Planet> notMyPlanets = state.NotMyPlanets();
		Random random = new Random();
		int source = myPlanets.get(random.nextInt(myPlanets.size())).PlanetID();
		int dest = notMyPlanets.get(random.nextInt(notMyPlanets.size())).PlanetID();
		
		state.IssueOrder(source, dest);
	}

	static void BreadthFirst(NewState state, int heuristicNumber){
		int searchDepth = 3;
		List<List<NewState>> stateTree = new ArrayList<List<NewState>>();
		List<NewState> levelOneFloor = new ArrayList<NewState>();
		levelOneFloor.add(state);

		stateTree.add(levelOneFloor);

		int bestHeuristic = Integer.MIN_VALUE;
		NewState bestState = null;

		for (int i = 0; i < searchDepth; i++)
		{
			List<NewState> currentFloor = stateTree.get(i);
			List<NewState> nextFloor = new ArrayList<NewState>();
			boolean endStateFound = false;
			for (NewState NewState : currentFloor)
			{
				// Hier voor de huidige state alle mogelijke volgende States toevoegen aan nextFloor
				for (Planet myPlanet : NewState.MyPlanets())
				{ 
					//*Tikkeltje Efficienter denk ik
					for(Planet planet : NewState.NotMyPlanets()){
						NewState stateToAdd = NewState.clone();
						stateToAdd.setParent(NewState);
						// Voer actie uit myPlanet valt neutralPlanet aan
						stateToAdd.SendFleet(myPlanet, planet);

						nextFloor.add(stateToAdd);
						int heuristic = stateToAdd.getScore(heuristicNumber);
						if (heuristic == Integer.MAX_VALUE)
						{
							// Eindstaat gevonden, stoppen met zoeken
							endStateFound = true;
							break;
						}
						else if (heuristic > bestHeuristic)
						{
							bestHeuristic = heuristic;
							bestState = stateToAdd;
						}
					}
					if (endStateFound)
						break;
				}
				if (endStateFound)
					break;
			}
			stateTree.add(nextFloor);
			if (endStateFound)
				break;
		}

		while (bestState.getParent() != state)
		{
			bestState = bestState.getParent();
		}

		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;

		//(3) Attack
		if (source != null && dest != null) {
			state.IssueOrder(source, dest);
		}
	}

	static void DepthFirst(NewState initialState){
		int searchDepth = 1;
		
		NewState bestState = visitState(initialState, searchDepth);
		
		while (bestState.getParent() != initialState)
		{
			bestState = bestState.getParent();
		}

		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;

		if (source != null && dest != null) {
			initialState.IssueOrder(source, dest);
		}
	}
	
	private static NewState visitState(NewState NewState, int searchDepth)
	{
		NewState result = NewState;
		
		if (searchDepth == 0)
			return result;
		
		int bestHeuristic = Heuristics.scoring1(NewState);
		boolean winStateFound = false;		
		
		// Returns best state found
		for (Planet myPlanet : NewState.MyPlanets())
		{
			for (Planet notMyPlanet : NewState.NotMyPlanets())
			{
				NewState stateToAdd = NewState.clone();
				stateToAdd.setParent(NewState);
				// Voer actie uit; myPlanet valt notMyPlanet aan
				stateToAdd.SendFleet(myPlanet, notMyPlanet);
				
				NewState bestResult = visitState(stateToAdd, searchDepth - 1);
				
				int heuristic = Heuristics.scoring1(bestResult);
				
				if (heuristic == Integer.MAX_VALUE )
				{
					result = bestResult;
					bestHeuristic = heuristic;
					winStateFound = true;
					break;
				}
				else if (heuristic > bestHeuristic)
				{
					result = bestResult;
					bestHeuristic = heuristic;
				}
			}
			if(winStateFound)
				break;
		}
			
		return result;
	}
	
	static void MinMax2(NewState pw, int heuristicNumber)
	{
		int searchDepth = 3;
		
		NewState bestState = MinMax2Recursion(pw, true, Integer.MAX_VALUE, searchDepth, heuristicNumber);
		while (bestState.getParent() != pw)
		{
			bestState = bestState.getParent();
		}

		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;

		if (source != null && dest != null) {
			pw.IssueOrder(source, dest);
		} 
	}
	
	private static NewState MinMax2Recursion(NewState state, boolean isMyTurn, int greek, int depth, int heuristicNumber)
	{	
		if (depth == 0)
			return state;

		int alpha = Integer.MIN_VALUE;
		int beta = Integer.MAX_VALUE;
		NewState bestState = state;
		for (NewState childState : state.getChildren(isMyTurn))
		{
			int greekNumber = isMyTurn ? alpha : beta;
			int childStateHeuristic = childState.getScore(heuristicNumber);
			if (childStateHeuristic == Integer.MAX_VALUE && isMyTurn) 
			{
				return childState;
			} 
			else if (childStateHeuristic == Integer.MIN_VALUE && !isMyTurn)
			{
				return childState;
			}
			NewState childResultState = MinMax2Recursion(childState, !isMyTurn, greekNumber, depth - 1, heuristicNumber);
			int heuristic = childResultState.getScore(heuristicNumber);
			if (isMyTurn)
			{
				if (heuristic > alpha)
				{
					bestState = childResultState;
					alpha = heuristic;
				}
				if (heuristic >= greek)
				{
					return bestState;
				}
			}
			else
			{
				if (heuristic < beta)
				{
					bestState = childResultState;
					beta = heuristic;
				}
				if (heuristic <= greek)
				{
					return bestState;
				}
			}
		}
		return bestState;
	}
	
	static List<NewState> possibleEnemyActions = null;
	static NewState previousEnemyAction = null;
	static NewState previousState = null;
	static NewState previousFriendlyAction = null;
	
	static void AdaptToEnemy(NewState pw, int heuristicNumber)
	{
		int searchDepth = 3;
		
		// Find out what move enemy has made
		if (previousState != null)
		{
			String compareString = pw.toString();
			for (NewState enemyAction : possibleEnemyActions)
			{
				NewState prevStateClone = previousState.clone();
				prevStateClone.SendFleetParallel(previousFriendlyAction.preActionSource, previousFriendlyAction.preActionDest, enemyAction.preActionSource, enemyAction.preActionDest);
				
				if (compareString.equalsIgnoreCase(prevStateClone.toString()))
				{
					previousEnemyAction = enemyAction;
					break;
				}
			}
			// Change enemy heuristic based on possibleEnemyActions list and previousEnemyAction
			Heuristics.adaptEnemyHeuristic(possibleEnemyActions, previousEnemyAction);
		}
		
		NewState bestState = ATERecursion(pw, true, Integer.MAX_VALUE, searchDepth, heuristicNumber);
		
		while (bestState.getParent() != pw)
		{
			bestState = bestState.getParent();
		}

		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;

		previousState = pw;
		previousFriendlyAction = bestState;
		possibleEnemyActions = pw.getChildren(false);
		
		if (source != null && dest != null) {
			pw.IssueOrder(source, dest);
		} 
	}
	
	private static NewState ATERecursion(NewState state, boolean isMyTurn, int greek, int depth, int heuristicNumber)
	{	
		if (depth == 0)
			return state;

		int alpha = Integer.MIN_VALUE;
		int beta = Integer.MAX_VALUE;
		NewState bestState = state;
		for (NewState childState : state.getChildren(isMyTurn))
		{
			int greekNumber = isMyTurn ? alpha : beta;
			int childStateHeuristic = childState.getScore(heuristicNumber);
			if (childStateHeuristic == Integer.MAX_VALUE && isMyTurn) 
			{
				return childState;
			} 
			else if (childStateHeuristic == Integer.MIN_VALUE && !isMyTurn)
			{
				return childState;
			}
			NewState childResultState = MinMax2Recursion(childState, !isMyTurn, greekNumber, depth - 1, heuristicNumber);
			int heuristic = isMyTurn ? childResultState.getScore(heuristicNumber) : Heuristics.enemyHeuristic(childResultState);
			if (isMyTurn)
			{
				if (heuristic > alpha)
				{
					bestState = childResultState;
					alpha = heuristic;
				}
				if (heuristic >= greek)
				{
					return bestState;
				}
			}
			else
			{
				if (heuristic < beta)
				{
					bestState = childResultState;
					beta = heuristic;
				}
				if (heuristic <= greek)
				{
					return bestState;
				}
			}
		}
		return bestState;
	}
	
	
}